package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author gorkr
 * @date 2022/09/14 11:49
 **/
public class M47PermutationsII {

    private List<List<Integer>> res = new LinkedList<>();
    private boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 排序
        Arrays.sort(nums);
        visited = new boolean[nums.length];
        backTracking(nums,new LinkedList<>());
        return res;
    }

    public void backTracking(int[] nums, LinkedList<Integer> trace){
        // base case
        if(trace.size()== nums.length){
            res.add(new ArrayList<>(trace));
            return;
        }

        // 选择
        for (int i = 0; i < nums.length; i++) {
            // 条件不对
            if(visited[i]){
                continue;
            }


            trace.add(nums[i]);
            visited[i] = true;
            backTracking(nums,trace);

            // 撤销
            visited[i] = false;
            trace.removeLast();
        }
    }

    @Test
    public void test(){
        System.out.println(permuteUnique(new int[]{1, 1, 2}).toString());
    }


}
    